package Aula20;

public class ArvoreBinaria {

	AVLNode raiz;
	
	public ArvoreBinaria(){
		super();
	}

	public AVLNode insert(int numero) {
		if(numero < 0){
			return null;
		}
		AVLNode novoAVLNode = new AVLNode(numero);
		AVLNode pai = null;
		AVLNode no = raiz;

		while (no != null) {
			pai = no;
			if(no.key == novoAVLNode.key){
				return null;
			}
			if (no.key > novoAVLNode.key) {
				no = no.left;
			} else{
				no = no.right;
			}
		}
		novoAVLNode.parent = pai;

		if (pai == null) {
			raiz = novoAVLNode;
		} else if (pai.key > novoAVLNode.key) {
			pai.left = novoAVLNode;
		} else {
			pai.right = novoAVLNode;
		}
		return novoAVLNode;
	}
	
	public AVLNode search(int key){
		if(key < 0){
			return null;
		}
		AVLNode no = raiz;
		if(no == null){
			return no;
		}
		while(no.key != key){
			if(key > no.key){
				if(no.right != null){
					no = no.right;
				}else{
					return null;
				}
			}else{
				if(no.left != null){
					no = no.left;
				}else{
					return null;
				}
			}
		}
		return no;
	}
	
	public AVLNode remove(int chave){
		if(chave == raiz.key){
			return null;
		}
		AVLNode no = search(chave);
		if (no == null){
			return null;
		}
		AVLNode noPai = no.parent;
		AVLNode left = no.left;
		AVLNode right = no.right;
		AVLNode noResposta = new AVLNode(chave);
		if (right ==  null && left == null)
			if(no.key > noPai.key)
				 noPai.right = null;
			else
				noPai.left = null;
		
		else if(left == null || right == null){
			if(right != null){
				if(no.key > noPai.key)
					 noPai.right = right;
				else
					noPai.left = right;
				right.parent = noPai;
			}else{
				if(no.key > noPai.key)
					 noPai.right = left;
				else
					noPai.left = left;
				left.parent = noPai;
			}
		}
		else{
			AVLNode substituto = right;
			while(substituto.left != null)
				substituto = substituto.left;
			remove(substituto.key);
			no.key = substituto.key;
		}
		return noResposta;
	}
	
	public static void main(String[] args) {
		ArvoreBinaria a = new ArvoreBinaria();
		a.raiz = new AVLNode(18);
		a.insert(20);
		a.insert(25);
		a.insert(27);
		a.insert(24);
		a.insert(26);
		a.insert(30);
		a.insert(10);
		
		System.out.println(a.remove(11));
		System.out.println(a.remove(25));
		System.out.println(a.raiz.right.right);
		System.out.println(a.remove(26));
		System.out.println(a.raiz.right.right);
		System.out.println(a.remove(18));
		System.out.println(a.raiz.right.right);
		System.out.println(a.raiz.right.right.left);
		System.out.println(a.remove(24));
		System.out.println(a.raiz.right.right.left);
		
		
	}

}
